#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class ZigZag {
public:
	int longestZigZag(vector <int>);
};

int ZigZag::longestZigZag(vector <int> seq) {
	int N = seq.size();
	vector<vector<int> > dp(2, vector<int>(N, 0));
	int ret = 0;
	for(int i=0; i<N; i++){
		dp[0][i] = 1;
		dp[1][i] = 1;
		for(int j=0; j<i; j++){
			if(seq[j]<seq[i]){
				dp[0][i] = min(dp[0][i], dp[1][j] + 1);
			}else if(seq[j]>seq[i]){
				dp[1][i] = min(dp[1][i], dp[0][j] + 1);
			}
		}
		ret = max(ret, max(dp[0][i], dp[1][i]));
	}
	return ret;
}


//Powered by [KawigiEdit] 2.0!
